洛谷 P4606 · 难度 NOI/NOI+/CTSC

题目描述

省选临近，放飞自我的小 Q 无心刷题，于是怂恿小 C 和他一起颓废，玩起了一款战略游戏。

这款战略游戏的地图由 $n$ 个城市以及 $m$ 条连接这些城市的双向道路构成，并且从任意一个城市出发总能沿着道路走到任意其他城市。

现在小 C 已经占领了其中至少两个城市，小 Q 可以摧毁一个小 C 没占领的城市，同时摧毁所有连接这个城市的道路。只要在摧毁这个城市之后能够找到某两个小 C 占领的城市 $u$ 和 $v$，使得从 $u$ 出发沿着道路无论如何都不能走到 $v$，那么小 Q 就能赢下这一局游戏。

小 Q 和小 C 一共进行了 $q$ 局游戏，每一局游戏会给出小 C 占领的城市集合 $S$，你需要帮小 Q 数出有多少个城市在他摧毁之后能够让他赢下这一局游戏。

输入格式

第一行包含一个正整数 $T$，表示测试数据的组数。

对于每组测试数据：

第一行是两个整数 $n$ 和 $m$ ，表示地图的城市数和道路数。

接下来 $m$ 行，每行包含两个整数 $u$ 和 $v(1\le u<v\le n)$，表示第 $u$ 个城市和第 $v$ 个城市之间有一条道路，同一对城市之间可能有多条道路连接。

第 $m+1$ 是一个整数 $q$，表示游戏的局数，

接下来 $q$ 行，每行先给出一个整数 $|S|(2\le |S|\le n)$，表示小 C 占领的城市数量，然后给出 $|S|$ 个整数 $(1\le S_1<S_2<\cdots <S_{|S|}\le n)$，表示小 C 占领的城市。

输出格式

对于每一局游戏，输出一行，包含一个整数，表示这一局游戏中有多少个城市在小 Q 摧毁之后能够让他赢下这一局游戏。

说明/提示

• $1\le T\le 10$；
• $2\le n\le {10}^5$ 且 $n-1\le m\le 2\times {10}^5$；
• $1\le q\le {10}^5$；
• 对于每组测试数据，有 $\sum |S|\le 2\times {10}^5$。

Subtasks

• 子任务 1 (30 分)：对于每组测试数据，满足 $\sum |S|\le 20$；
• 子任务 2 (45 分)：对于每一次询问，满足 $|S|=2$；
• 子任务 3 (25 分)：没有任何附加的限制。

样例

样例 1

输入

2
7 6
1 2
1 3
2 4
2 5
3 6
3 7
3
2 1 2
3 2 3 4
4 4 5 6 7
6 6
1 2
1 3
2 3
1 4
2 5
3 6
4
3 1 2 3
3 1 2 6
3 1 5 6
3 4 5 6

输出

0
1
3
0
1
2
3